// Copyright 2000-2023 JetBrains s.r.o. and contributors. Use of this source code is governed by the Apache 2.0 license.
package com.intellij.util.containers.hash;

import java.util.Arrays;

final class HashUtil {
  static final int MIN_CAPACITY = 5;

  static final float CAPACITY_MULTIPLE = 1.618033989f;

  static int adjustTableSize(int size) {
    int i = Arrays.binarySearch(tableSizes, size);
    if (i < 0) {
      i = ~i;
    }

    return tableSizes[i];
  }

  // must be sorted: Arrays.stream(tableSizes).sorted().mapToObj(it -> Integer.toString(it)).collect(Collectors.joining(","))
  private static final int[] tableSizes = {
    // include all odd primes under 1000

    3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137,
    139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
    283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449,
    457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619,
    631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811,
    821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997,
    1031, 1091, 1153, 1217, 1283, 1361, 1409, 1481, 1543, 1601, 1667, 1733, 1801, 1861, 1931, 1993, 2063, 2203, 2309, 2437, 2579, 2729,
    2819, 2963, 3089, 3203, 3343, 3467, 3607, 3727, 3863, 3989, 4127, 4409, 4621, 4877, 5167, 5471, 5639, 5927, 6197, 6421, 6689, 6947,
    7219, 7457, 7727, 7993, 8263, 8819, 9257, 9767, 10337, 10949, 11279, 11863, 12401, 12853, 13381, 13901, 14447, 14923, 15461, 15991,
    16529, 17657, 18517, 19541, 20681, 21911, 22567, 23741, 24809, 25717, 26777, 27803, 28901, 29851, 30931, 31991, 33071, 35317, 37039,
    39089, 41381, 43853, 45137, 47491, 49627, 51437, 53569, 55609, 57803, 59707, 61871, 63997, 66161, 70639, 74093, 78179, 82763, 87719,
    90281, 94993, 99257, 102877, 107171, 111227, 115613, 119417, 123757, 127997, 132329, 141283, 148193, 156361, 165527, 175447, 180563,
    189989, 198529, 205759, 214351, 222461, 231241, 238837, 247519, 256019, 264659, 282571, 296437, 312727, 331063, 350899, 361159, 379979,
    397063, 411527, 428731, 444929, 462491, 477677, 495041, 512047, 529327, 565163, 592877, 625477, 662141, 701819, 722321, 759959, 794137,
    823117, 857471, 889871, 924997, 955363, 990137, 1024099, 1058657, 1130351, 1185787, 1250969, 1324313, 1403641, 1444649, 1519939,
    1588289, 1646237, 1714957, 1779761, 1850021, 1910729, 1980281, 2048203, 2117317, 2260717, 2371609, 2501953, 2648629, 2807303, 2889317,
    3039917, 3176597, 3292489, 3429961, 3559537, 3700043, 3821483, 3960581, 4096427, 4234651, 4521509, 4743223, 5003909, 5297287, 5614657,
    5778649, 6079861, 6353213, 6584983, 6859933, 7119103, 7400123, 7643017, 7921169, 8192867, 8469319, 9043033, 9486469, 10007819, 10594583,
    11229331, 11557303, 12159731, 12706451, 13169977, 13719869, 14238221, 14800271, 15286079, 17135863, 18366923, 19845871, 21006137,
    22458671, 23723597, 25002389, 26339969, 28977863, 31322867, 34271747, 36733847, 39691759, 42012281, 44917381, 47447201, 50004791,
    52679969, 57955739, 62645741, 68543509, 73467739, 79383533, 84024581, 89834777, 94894427, 100009607, 105359939, 115911563, 125291483,
    137087021, 146935499, 158767069, 168049163, 179669557, 189788857, 200019221, 210719881, 231823147, 250582987, 274174111, 293871013,
    317534141, 336098327, 359339171, 379577741, 400038451, 421439783, 463646329, 501165979, 548348231, 587742049, 635068283, 672196673,
    718678369, 759155483, 800076929, 842879579, 927292699, 1002331963, 1096696463, 1175484103, 1270136683, 1344393353, 1437356741,
    1518310967, 1600153859, 1685759167, 1854585413, 2004663929, 2147483647, Integer.MAX_VALUE,
  };
}

